﻿namespace AdvancedTraining.Lesson50;

/// <summary>
/// 最大休假天数问题 - LeetCode 568
/// 使用动态规划计算在K周内能够在N个城市之间飞行获得的最大休假天数
/// </summary>
public class MaximumVacationDays //leetcode_0568
{
    /// <summary>
    /// 计算最大休假天数
    /// 算法思路：动态规划
    /// 1. 预处理每个城市可以从哪些城市飞达
    /// 2. dp[i][j]表示第i周在城市j能获得的最大休假天数
    /// 3. 状态转移：dp[i][j] = max(dp[i-1][j], max(dp[i-1][p] for p in pass[j])) + day[j][i]
    /// 4. 最后结果为最后一周在任意城市的最大值
    /// 时间复杂度：O(K * N²)，K为周数，N为城市数
    /// 空间复杂度：O(K * N)
    /// </summary>
    /// <param name="fly">飞行矩阵，fly[i][j]=1表示可以从城市i飞到城市j</param>
    /// <param name="day">休假矩阵，day[i][j]表示第j周在城市i的休假天数</param>
    /// <returns>最大休假天数</returns>
    public static int MaxVacationDays(int[][] fly, int[][] day)
    {
        var n = fly.Length;
        var k = day[0].Length;

        // pass[i] = {a, b, c}
        // 从a、b、c能飞到i
        var pass = new int[n][];
        for (var i = 0; i < n; i++)
        {
            var s = 0;
            for (var j = 0; j < n; j++)
                if (fly[j][i] != 0)
                    s++;
            pass[i] = new int[s];
            for (var j = n - 1; j >= 0; j--)
                if (fly[j][i] != 0)
                    pass[i][--s] = j;
        }

        // dp[i][j] -> 第i周必须在j这座城，0~i-1周（随意），最大休假天数
        var dp = new int[k][];
        for (var i = 0; i < k; i++)
            dp[i] = new int[n];

        // 飞的时机，是周一早上飞，认为对时间没有影响，直接到某个城，然后过一周
        dp[0][0] = day[0][0];
        for (var j = 1; j < n; j++)
            dp[0][j] = fly[0][j] != 0 ? day[j][0] : -1;

        for (var i = 1; i < k; i++)
        {
            // 第i周
            for (var j = 0; j < n; j++)
            {
                // 在j号城过！
                // 第i周，要怎么到j号城
                // 下面max的初始值，我第i-1周，就在j号城，选择不动地方，进入第i周
                var max = dp[i - 1][j];
                foreach (var p in pass[j])
                {
                    // 枚举什么？能到j号城的城市p
                    max = Math.Max(max, dp[i - 1][p]);
                }
                dp[i][j] = max != -1 ? max + day[j][i] : -1;
            }
        }

        var ans = 0;
        for (var i = 0; i < n; i++)
            ans = Math.Max(ans, dp[k - 1][i]);
        return ans;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 最大休假天数问题测试 ===");

        // 测试用例1: LeetCode官方示例
        Test1();

        // 测试用例2: 无法飞行的情况
        Test2();

        // 测试用例3: 只有一个城市
        Test3();

        // 测试用例4: 完全连通图
        Test4();

        // 测试用例5: 一周的情况
        Test5();

        // 测试用例6: 复杂飞行网络
        Test6();

        Console.WriteLine("\n=== 算法说明 ===");
        Console.WriteLine("动态规划：dp[i][j]表示第i周在城市j的最大休假天数");
        Console.WriteLine("状态转移：可以从上一周同一城市不动，或从能飞到当前城市的任意城市飞来");
        Console.WriteLine("预处理：提前计算每个城市可以从哪些城市飞达，优化状态转移");
        Console.WriteLine("时间复杂度：O(K * N²)，空间复杂度：O(K * N)");
    }

    /// <summary>
    /// 测试用例1: LeetCode官方示例
    /// </summary>
    private static void Test1()
    {
        Console.WriteLine("\n测试用例1: LeetCode官方示例");
        int[][] flights = [[0, 1, 1], [1, 0, 1], [1, 1, 0]];
        int[][] days = [[1, 3, 1], [6, 0, 3], [3, 3, 3]];
        var result = MaxVacationDays(flights, days);
        Console.WriteLine($"飞行矩阵: [{string.Join(", ", flights.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"休假矩阵: [{string.Join(", ", days.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"最大休假天数: {result} (期望: 12)");
    }

    /// <summary>
    /// 测试用例2: 无法飞行的情况
    /// </summary>
    private static void Test2()
    {
        Console.WriteLine("\n测试用例2: 无法飞行的情况");
        int[][] flights = [[1, 0, 0], [0, 1, 0], [0, 0, 1]];
        int[][] days = [[1, 2, 3], [3, 2, 1], [2, 1, 3]];
        var result = MaxVacationDays(flights, days);
        Console.WriteLine($"飞行矩阵: [{string.Join(", ", flights.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"休假矩阵: [{string.Join(", ", days.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"最大休假天数: {result} (期望: 6，只能在城市0)");
    }

    /// <summary>
    /// 测试用例3: 只有一个城市
    /// </summary>
    private static void Test3()
    {
        Console.WriteLine("\n测试用例3: 只有一个城市");
        int[][] flights = [[1]];
        int[][] days = [[5, 7, 2]];
        var result = MaxVacationDays(flights, days);
        Console.WriteLine($"飞行矩阵: [{string.Join(", ", flights.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"休假矩阵: [{string.Join(", ", days.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"最大休假天数: {result} (期望: 14)");
    }

    /// <summary>
    /// 测试用例4: 完全连通图
    /// </summary>
    private static void Test4()
    {
        Console.WriteLine("\n测试用例4: 完全连通图");
        int[][] flights = [[1, 1, 1], [1, 1, 1], [1, 1, 1]];
        int[][] days = [[1, 2, 3], [3, 2, 1], [2, 3, 1]];
        var result = MaxVacationDays(flights, days);
        Console.WriteLine($"飞行矩阵: [{string.Join(", ", flights.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"休假矩阵: [{string.Join(", ", days.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"最大休假天数: {result} (期望: 9，每周选择休假天数最多的城市)");
    }

    /// <summary>
    /// 测试用例5: 一周的情况
    /// </summary>
    private static void Test5()
    {
        Console.WriteLine("\n测试用例5: 一周的情况");
        int[][] flights = [[0, 1, 0], [0, 0, 1], [1, 0, 0]];
        int[][] days = [[1], [2], [3]];
        var result = MaxVacationDays(flights, days);
        Console.WriteLine($"飞行矩阵: [{string.Join(", ", flights.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"休假矩阵: [{string.Join(", ", days.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"最大休假天数: {result} (期望: 2，从城市0无法直接到达城市2)");
    }

    /// <summary>
    /// 测试用例6: 复杂飞行网络
    /// </summary>
    private static void Test6()
    {
        Console.WriteLine("\n测试用例6: 复杂飞行网络");
        int[][] flights = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]];
        int[][] days = [[4, 2, 1, 3], [2, 3, 4, 1], [1, 4, 3, 2], [3, 1, 2, 4]];
        var result = MaxVacationDays(flights, days);
        Console.WriteLine($"飞行矩阵: [{string.Join(", ", flights.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"休假矩阵: [{string.Join(", ", days.Select(row => $"[{string.Join(",", row)}]"))}]");
        Console.WriteLine($"最大休假天数: {result} (期望: 14，可以灵活选择最优路径)");
    }
}